
/*
Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

*/

#include <iostream>
#include <string>
#include <vector>
using namespace std;

/**
* Definition for singly-linked list.
*/
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	ListNode * removeElements(ListNode *head, int val)
	{
		ListNode **list = &head;

		while (*list != nullptr)
		{
			if ((*list)->val == val)
			{
				*list = (*list)->next;
			}
			else
			{
				list = &(*list)->next;
			}
		}

		return head;
	}

	ListNode * removeElements2(ListNode *head, int val) {
		if (head == nullptr) return nullptr;
		head->next = removeElements2(head->next, val);
		return head->val == val ? head->next : head;
	}

	ListNode* removeElements1(ListNode* head, int val) {
		ListNode *pseudo_head = new ListNode(0);
		pseudo_head->next = head;
		ListNode *cur = pseudo_head;
		while (cur) 
		{
			if (cur->next && cur->next->val == val)   
				cur->next = cur->next->next;
			else
				cur = cur->next;
		}
		return pseudo_head->next;
	}

	ListNode* removeElements1_1(ListNode* head, int val) {
		ListNode pseudo_head(0);
		pseudo_head.next = head;
		ListNode *prev = &pseudo_head;
		ListNode *cur = prev->next;
		while (cur) {
			if (cur->val == val)   prev->next = cur->next;
			else    prev = prev->next;
			cur = cur->next;
		}
		return pseudo_head.next;
	}


	ListNode * removeElements0(ListNode* head, int val) {
		ListNode *p = head;
		ListNode *h = head;
		ListNode *pre = nullptr;
		ListNode *cur = nullptr;
		while (p != nullptr)
		{
			if (p->val == val)
			{
				if (pre != nullptr)
				{
					pre->next = p->next;
					cur = p;
					p = p->next;
					//free(cur);
					delete cur;
				}
				else
				{
					cur = p;
					p = cur->next;
					h = cur->next;
					//free(cur);
					delete cur;
				}
			}
			else
			{
				pre = p;
				p = p->next;
			}
		}

		return h;
	}

};

int _removeElements()
{
	typedef struct {
		vector<int> e;
		int v;
	} CASE;

	CASE case1{ { 1,2,6,3,4,5,6 },6 };
	CASE case2{ { 1},1 };

	CASE testcase = case1;
	Solution solu;
	ListNode prehead(0), * list = &prehead;
	ListNode * result = nullptr;
	ListNode * t = nullptr;
	
	for (auto num : testcase.e)
	{
		t = new ListNode(num);
		list->next = t;
		list = t;
	}

	list = prehead.next;

	result = solu.removeElements(list, testcase.v);

	cout << "raw: " << endl;
	for (auto num : testcase.e)
		cout << num << " ";
	cout << endl;

	cout << "value: " << testcase.v << endl;

	cout << "result: " << endl;
		
	t = result;
	while (t != NULL)
	{
		cout << t->val << " ";
		t = t->next;
	}
	cout << endl;

	return 0;
}